package class3;

import common.ListNode;
import common.ListNodeUtils;


public class Code21_LinkedSort {
    public static void main(String[] args) {
        ListNode listNode = ListNodeUtils.getLinked(4,19,14,5,-3,1,8,5,11,15);
        ListNodeUtils.print(linkedSort(listNode));

    }

    // 归并排序
    public static ListNode linkedSort(ListNode listNode) {
        int k = 0;
        ListNode cur = listNode;
        while (cur != null) {
            cur = cur.next;
            k++;
        }
        int[] arr = new int[k];
        cur = listNode;
        for (int i = 0; i < arr.length; i++) {
            arr[i] = cur.val;
            heapInsert(arr, i);
            cur = cur.next;
        }

        int heapSize = arr.length - 1;
        heapify(arr, 0, heapSize);
        while (heapSize > 0) {
            swap(arr, 0, heapSize);
            heapify(arr, 0, heapSize--);
        }
        ListNode head = new ListNode(arr[0]);
        ListNode last = head;
        for (int i = 1; i < arr.length; i++) {
            last.next = new ListNode(arr[i]);
            last = last.next;
        }
        return head;
    }

    // 上浮
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    // 下沉
    public static void heapify(int[] arr, int index, int heapSize) {
        int left = (index << 1) | 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; // 取左右节点较大的
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, index, largest);
            index = largest;
            left = (index << 1) | 1;
        }
    }

    public static void swap(int[] arr, int x, int y) {
        int t = arr[x];
        arr[x] = arr[y];
        arr[y] = t;
    }


}
